// const Queue = require("yocto-queue");
// import Queue from "yocto-queue"; // 不行，没有remove方法

/**
 * Definition for a binary tree node. */
function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}


// 字符串转二叉树
/**
 * @param {string} input
 * @return {TreeNode}
 */
const stringToTreeNode = function(input) {
    input = input.trim()
    input = input.substring(1, input.length-1);
    if (input.length === 0) {
        return null;
    }
    const parts = input.split(",");
    let item = parts[0];
    let root = TreeNode(parseInt(item));
    // 同目录不用引入！！
    const nodeQueue = new MyQueue();
    nodeQueue.push(root);
    let index = 1;
    while (!nodeQueue.empty()) {
        let node = nodeQueue.pop();

        if (index === parts.length) {
            break;
        }

        item = parts[index++];
        item = item.trim();
        if (item !== "null") {
            let leftNumber = parseInt(item);
            // Value assigned to primitive will be lost ?? !! -> 估计要改！
            node.left = TreeNode(leftNumber);
            nodeQueue.push(node.left);
        }
        // 提示重复，这个应该不是故意重复的？！
        // if (index === parts.length) {
        //     break;
        // }

        item = parts[index++];
        item = item.trim();
        if (item !== "null") {
            let rightNumber = parseInt(item);
            // Value assigned to primitive will be lost ?? !!
            node.right = TreeNode(rightNumber);
            nodeQueue.push(node.right);
        }
    }
    return root;
}

/**
 * @param {TreeNode} root
 * @return {string}
 */
const treeNodeToString = function (root) {
    if (root == null) {
        return "[]";
    }
    let output = "";
    // 同目录不用引入！！
    const nodeQueue = new MyQueue();
    nodeQueue.push(root);
    while (!nodeQueue.empty()) {
        let node= nodeQueue.pop();
        if (node == null) {
            output += "null, ";
            continue;
        }
        output += node.val + ", ";
        nodeQueue.push(node.left);
        nodeQueue.push(node.right);
    }
    return "[" + output.substring(0, output.length-2) + "]";
}

/**
 * @param {TreeNode} node
 * @param {string} prefix
 * @param {boolean} isLeft
 * @return {string}
 */
const prettyPrintTree = function (node, prefix, isLeft) {
    if (node === null) {
        console.log("Empty tree");
        return;
    }
    if (node.right !== null) {
        prettyPrintTree(node.right, prefix + (isLeft ? "│   " : "    "), false);
    }
    console.log(prefix + (isLeft ? "└── " : "┌── ") + node.val);
    if (node.left !== null) {
        prettyPrintTree(node.left, prefix + (isLeft ? "    " : "│   "), true);
    }
}

// 和java不一样，不能和上面同名 prettyPrintTree 报错！
/**
 * @param {TreeNode} node
 * @return {string}
 */
const prettyPrintTreeNode = function(node) {
    prettyPrintTree(node,  "", true);
}

// 外部目录引用
module.exports = prettyPrintTreeNode;
module.exports = treeNodeToString;
module.exports = stringToTreeNode;
